Although nowadays there are many compression methods of binary images, they cannot be directly applied to compress encrypted binary images. In scenarios like cloud computing and distributed computing, how to perform lossy compression efficiently on encrypted binary images remains a challenge, and there are few researches focusing on it. Aiming at this problem, a lossy compression algorithm for encrypted binary images using Markov Random Field (MRF) were proposed. MRF was used to characterize the spatial statistics of binary image, and MRF as well as the decompressed pixels was used to deduce those pixels discarded in the compression process of encrypted binary image. In the proposed algorithm, the stream cipher was used by the sender to encrypt the binary image, the subsampling method with uniform blocks and random in the block and Low-Density Parity-Check (LDPC)-based encoding were employed by the cloud server to compress the encrypted binary image, and the joint factor graph including the decoding, decryption and MRF-based reconstruction was constructed by the receiver to realize the lossy reconstruction of the binary image. The experimental results show that the proposed algorithm achieves desirable compression efficiency with the Bit Error Rate (BER) of the lossy reconstructed binary image smaller than 5% when compression rate is 0.2 to 0.4 bpp (bit per pixel). When compared with the compression efficiency of the international compression standard JBIG2 (Joint Bi-level Image experts Group version 2) of original unencrypted binary images, the proposed algorithm obtains the comparable compression efficiency. These fully demonstrate the feasibility and effectiveness of the proposed algorithm.